package J20241118_Slide;
import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description: 滑动窗口——串联所有单词的⼦串
 * User: 王圆豪
 * Date: 2024-11-18
 * Time: 20:22
 */

public class Solution {

    public static void main(String[] args) {
        System.out.println(findSubstring("aaaaaaaaaaaaaa", new String[]{"aa", "aa"}).toString());
    }
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        int part = words[0].length();
        int sum = words.length * part;
        HashMap<String, Integer> hash1 = new HashMap<>();
        for(String ss : words){
            hash1.put(ss, hash1.getOrDefault(ss, 0) + 1);
        }
        for(int j = 0; j < part; j++){
            int count = 0;
            HashMap<String, Integer> hash2 = new HashMap<>();
            int l = j;
            for(int r = l; r + part <= s.length(); r += part){
                String s1 = s.substring(r ,r + part);
                hash2.put(s1, hash2.getOrDefault(s1, 0) + 1);
                if(hash2.getOrDefault(s1, 0) <= hash1.getOrDefault(s1, 0)){
                    count++;
                }
                if(r - l + 1> sum){
                    String s2 = s.substring(l, l + part);
                    if(hash2.getOrDefault(s2, 0) <= hash1.getOrDefault(s2, 0)){
                        count--;
                    }
                    hash2.put(s2, hash2.getOrDefault(s2, 0) - 1);
                    if(hash2.getOrDefault(s2, 0) == 0){
                        hash2.remove(s2);
                    }
                    l += part;
                }
                if(count == words.length) ret.add(l);
            }
        }
        return ret;
    }
}
